#include "graph_reduction.h"
//#include "../graph/graph.h"

#define BENCH

void graph_reduction::load_graph(char* benchmark, class ff_graph& ff_obj)
{
    char graph_file[50];
#ifndef ITC99
    strcpy(graph_file, "../benchmark/BENCH/cloud/");
#else
    strcpy(graph_file, "../benchmark/ITC99/cloud/");
#endif
    strcat(graph_file, benchmark);

    strcat(graph_file, "_p2.dag"); //phase two

    FILE *fp = fopen (graph_file, "r");

    if (graph_file == NULL) 
    {
        perror ("Error opening partition graph file");
    }
    else
    {
        rewind(fp); //jump to file beginning

        //initial a temp edge struct
        edge e; 
        e.in = 0;
        e.out = 0;
        e.delay = 0.0;

        unsigned int vertex_num, edge_num, temp;
        //fscanf(fp, " %d %d %d\n", &vertex_num, &ff_obj.ff_num, &edge_num);
        fscanf(fp, " %d %d %d\n", &vertex_num, &temp, &edge_num);
        
        //ff_obj.set_vertex_num(vertex_num);
        assert(vertex_num == ff_obj.get_vertex_num());

        ff_obj.set_edge_num(edge_num);

        while (!feof(fp)) 
        {
            fscanf(fp," %d %d\n", &e.in, &e.out);
            ff_obj.edge_set.push_back(e);
        }

        //check the integrity 
        assert(edge_num == ff_obj.edge_set.size());
    }

    fclose(fp);

    //generate adjacent lists
    ff_obj.gen_fanouts();
    ff_obj.gen_fanins();
}

void graph_reduction::load_vertex_delay(char* benchmark, class ff_graph& ff_obj)
{
    char delay_file[50];
#ifndef ITC99
    strcpy(delay_file, "../benchmark/BENCH/cloud/");
#else
    strcpy(delay_file, "../benchmark/ITC99/cloud/");
#endif
    strcat(delay_file, benchmark);
    strcat(delay_file, "_p2.delay"); //phase two
    
    FILE *fp = fopen(delay_file,"r");

    if (fp == NULL) 
    {
        perror ("Error opening delay file");
    }
    else
    {
        rewind(fp);

        unsigned int delay_num;
        unsigned int v = 0; //vertex
        float pca; //single pca component
        unsigned int color; 
        unsigned long seed; 

        fscanf(fp," %d %d \n", &delay_num, &ff_obj.delay_column);
        
        ff_obj.set_vertex_num(delay_num);

        ff_obj.initial_vertex_color(); //initial vertex_color

        ff_obj.vertex_delay.assign(ff_obj.get_vertex_num(), 
                            vector<float>(ff_obj.delay_column, 0));

        ff_obj.tp_order.clear();

        while (!feof(fp)) 
        {
            //fscanf(fp," %d", &v);
            ff_obj.tp_order.push_back(v);

            fscanf(fp," %d %d", &color, &seed);
            ff_obj.set_vertex_color(v, color);
            mc_vertex_seed.push_back(seed);
            
            if (color == 1)
            {
                gray_set.push_back(v);
            }

            for (unsigned int j = 0; j < ff_obj.delay_column; j++)
            {
                fscanf(fp," %f", &pca);
                ff_obj.vertex_delay[v][j] = pca;
            }                
            fscanf(fp," \n");

            v++; //phase two, delay store by tp_order
        }
        
        //check the integrity
        assert(v == delay_num);
    }

    fclose (fp);
}

void graph_reduction::gen_mc_delay(class ff_graph& ff_obj, unsigned int ith_mc)
{
    //default_random_engine normal_generator;
    normal_distribution<float> distribution(0, 1);

    // the Mersenne Twister with a popular choice of parameters
    typedef std::mt19937 MyRNG;  
    MyRNG rng;                   // e.g. keep one global instance (per thread)

    // generate deterministic delay for each simulation
    mc_vertex_delay.assign(ff_obj.get_vertex_num(), 0);

    for (unsigned int i = 0; i < ff_obj.get_vertex_num(); i++) 
    {
        // mean of random delay
        /*
        * Implementation note:
        *  We should simulate all falling and rising delays
        *  Current design is for simplicity
        */

        //gray vertex without fanout
        if (ff_obj.vertex_fanout[i].empty() && ff_obj.get_vertex_color(i) == 1)
        {
            continue;
        }

        //unsigned int delay_num = ff_obj.vertex_fanin.size() * 2;
        unsigned int delay_num = 1;

        vector <float> delays; //store all delays for single gate 
        delays.assign(delay_num, 0);

        //seed reproduce
        unsigned long rand_seed = 100 + (ith_mc + 1) * (mc_vertex_seed[i] - 100);
        rng.seed(rand_seed);

        for (unsigned int k = 0; k < delay_num; k++)
        {
            //delays[k] = ff_obj.vertex_delay[i][0] - k* 0.1; //mean 
            delays[k] = ff_obj.vertex_delay[i][0];
            for (unsigned int j = 1; j < VARNUM; j++) 
            {
                float rand = distribution(rng);
                delays[k] += ff_obj.vertex_delay[i][j] * rand;
            }
        }

        float delay = *max_element(delays.begin(),delays.end());

        if (delay < 0) {
            delay = 0.0; //in case generate negative delay
        }
        mc_vertex_delay[i] = delay;
    }

    for (unsigned int i = 0; i < ff_obj.get_vertex_num(); i++) 
    {
        //assign gate's weight to fanout edge 
        vector<edge>::iterator edge_it;
        for (edge_it = ff_obj.vertex_fanout[i].begin(); 
            edge_it != ff_obj.vertex_fanout[i].end(); ++edge_it)
        {
            (*edge_it).delay = mc_vertex_delay[i];
        }

        for (edge_it = ff_obj.vertex_fanin[i].begin(); 
            edge_it != ff_obj.vertex_fanin[i].end(); ++edge_it)
        {
            (*edge_it).delay = mc_vertex_delay[(*edge_it).in];
        }
    }
}

struct edge graph_reduction::edge_exist(unsigned int source, 
                                    unsigned int sink, class ff_graph& ff_obj)
{
    struct edge fanout;
    fanout.in = 0;
    fanout.out = 0;
    fanout.delay = 0.0;

    vector<edge>::iterator fanout_it; 
    for (fanout_it = ff_obj.vertex_fanout[source].begin(); 
        fanout_it != ff_obj.vertex_fanout[source].end(); ++fanout_it)
    {
        if (sink == (*fanout_it).out)
        {
            return *fanout_it;
        }
    }

    return fanout;
}

bool graph_reduction::fanin_delete(struct edge fanin, class ff_graph& ff_obj)
{
    // delete e_ik from v_k fanin
    unsigned int v_k = fanin.out;
    vector<edge>::iterator fanin_it;
    for (fanin_it = ff_obj.vertex_fanin[v_k].begin(); 
        fanin_it != ff_obj.vertex_fanin[v_k].end(); ++fanin_it)
    {
        struct edge e = *fanin_it;
        unsigned int v_i = e.in;
        if (v_i == fanin.in) 
        {
            ff_obj.vertex_fanin[v_k].erase(fanin_it);
            return true;
        }
    }

    return false;
}

bool graph_reduction::fanout_delete(struct edge fanout, class ff_graph& ff_obj)
{
    // delete e_ji from v_j fanout;
    unsigned int v_j = fanout.in;
    vector<edge>::iterator fanout_it;
    for (fanout_it = ff_obj.vertex_fanout[v_j].begin(); 
        fanout_it != ff_obj.vertex_fanout[v_j].end(); ++fanout_it)
    {
        struct edge e = *fanout_it;
        unsigned int v_i = e.out;
        if (v_i == fanout.out) 
        {
            ff_obj.vertex_fanout[v_j].erase(fanout_it);
            return true;
        }
    }

    return false;
}

void graph_reduction::vertex_elimination(unsigned int v_i, 
                                    class ff_graph& ff_obj)
{

#ifdef ITC99
    if (ff_obj.vertex_fanout[v_i].empty())
    {
        for (unsigned int j = 0; j < ff_obj.vertex_fanin[v_i].size(); ++j)
        {
            struct edge edge_ji = ff_obj.vertex_fanin[v_i][j]; //edge_ji
            assert(true == fanout_delete(edge_ji, ff_obj));
        }
        ff_obj.vertex_fanin[v_i].clear();
    }
    
    if (ff_obj.vertex_fanin[v_i].empty())
    {
        for (unsigned int j = 0; j < ff_obj.vertex_fanout[v_i].size(); ++j)
        {
            struct edge edge_ji = ff_obj.vertex_fanout[v_i][j]; //edge_ji
            assert(true == fanin_delete(edge_ji, ff_obj));
        }
        ff_obj.vertex_fanout[v_i].clear();
    }
#endif

    for (unsigned int k = 0; k < ff_obj.vertex_fanout[v_i].size(); ++k)
    {
        struct edge edge_ik = ff_obj.vertex_fanout[v_i][k];
        unsigned int v_k = edge_ik.out; //v_k as sink in paper

        for (unsigned int j = 0; j < ff_obj.vertex_fanin[v_i].size(); ++j)
        {
            struct edge edge_ji = ff_obj.vertex_fanin[v_i][j]; //edge_ji
            unsigned int v_j = edge_ji.in;  //v_j as source in paper

            struct edge edge_jk = edge_exist(v_j, v_k, ff_obj);

            if (edge_jk.in == 0 && edge_jk.out == 0) //invalid edge 
            {
                // insert edge_{source, sink}
                edge_jk.in = v_j;
                edge_jk.out = v_k;

                // w_jk = w_ji + w_i;
                edge_jk.delay = edge_ji.delay + mc_vertex_delay[v_i];

                // insert to fanout of j
                ff_obj.vertex_fanout[v_j].push_back(edge_jk);

                // insert to fanin of k
                ff_obj.vertex_fanin[v_k].push_back(edge_jk);
            }
            else
            {
                // w_jk = max{w_jk, w_ji + w_i};
                float delay = edge_ji.delay + mc_vertex_delay[v_i];
                delay = (edge_jk.delay > delay) ? edge_jk.delay : delay;
            }
        }
    }

    // delete v_i
    vector<edge>::iterator fanout_it;
    for (fanout_it = ff_obj.vertex_fanout[v_i].begin(); 
        fanout_it != ff_obj.vertex_fanout[v_i].end(); ++fanout_it)
    {
        struct edge edge_ik = *fanout_it; //delete edge_i,k from k's fanin
        fanin_delete(edge_ik, ff_obj);
    }
    ff_obj.vertex_fanout[v_i].clear();

    vector<edge>::iterator fanin_it;
    for (fanin_it = ff_obj.vertex_fanin[v_i].begin(); 
        fanin_it != ff_obj.vertex_fanin[v_i].end(); ++fanin_it)
    {
        struct edge edge_ji = *fanin_it; //delete edge_j,i from j's fanout
        fanout_delete(edge_ji, ff_obj);
    }
    ff_obj.vertex_fanin[v_i].clear();
    
}

void graph_reduction::write_reduce_graph(char* benchmark, 
                                        class ff_graph& ff_obj)
{
    char rd_file[50];
#ifndef ITC99
    strcpy(rd_file, "../benchmark/BENCH/local/");
#else
    strcpy(rd_file, "../benchmark/ITC99/local/");
#endif
    strcat(rd_file, benchmark);

    strcat(rd_file, "_rd_p2.dag"); //phase two
    
    FILE *fp = fopen(rd_file, "w");

    if (fp == NULL) 
    {
        perror ("Error opening graph reduction file");
    }
    
    fprintf(fp,"                \n");
    unsigned int edge_num = 0;

    set<set<unsigned int> >::iterator it1;
    set<unsigned int >::iterator it2;
    //gray_longest_path_depth.assign(gray_set.size(), 0);

    int index = 0;
    for (it1 = gray_reach_list.begin(); it1 != gray_reach_list.end(); it1++)
    {
        vector<edge> cur_path_set;
        for (it2 = (*it1).begin(); it2 != (*it1).end(); it2++)
        {
            if (it2 == (*it1).begin()) continue;

            fprintf(fp, "%d %d\n", *((*it1).begin()), (*it2));
            struct edge e;
            e.in = *((*it1).begin());
            e.out = (*it2);

            //update longest path depth
            assert(e.out > e.in);
            //gray_longest_path_depth[index] = 
                //((e.out - e.in) > gray_longest_path_depth[index]) 
                //? (e.out - e.in) : gray_longest_path_depth[index];

            cur_path_set.push_back(e);
            edge_num++;
        }
        gray_path_set.push_back(cur_path_set);
        index++;
    }

    rewind(fp);
    fprintf(fp, "%d", edge_num);
    fclose(fp);
}

void graph_reduction::partial_sta(class ff_graph& ff_obj)
{
    //iterative PERT
    for (unsigned int i = 0; i < gray_set.size(); i++) 
    {
        //ignore gray one without outgoing edges
        unsigned int prime_source = gray_set[i];

        if (ff_obj.vertex_fanout[prime_source].empty()) continue;

        //reset arrive time for each gray starting vertex
        vertex_arrive_time.assign(ff_obj.get_vertex_num(), 0); 

        //exist tag in reachable list of v_i
        vector<unsigned int> reachable_tag;
        reachable_tag.assign(ff_obj.get_vertex_num(), 0); 

        reachable_tag[prime_source] = 1; //reachable

        //PERT
        for (unsigned int vertex = prime_source + 1; 
                        vertex < ff_obj.get_vertex_num(); vertex++)
        {         
            vector<edge>::iterator edge_it;
            for (edge_it = ff_obj.vertex_fanin[vertex].begin(); 
                edge_it != ff_obj.vertex_fanin[vertex].end(); ++edge_it)
            {
                unsigned int source = (*edge_it).in;
                if (reachable_tag[source] == 0) continue; //not reachable

                //accumulate path delay
                
                float temp_delay = (*edge_it).delay + vertex_arrive_time[source];

                //update arrive time
                vertex_arrive_time[vertex] = 
                    (vertex_arrive_time[vertex] > temp_delay) 
                    ? vertex_arrive_time[vertex] : temp_delay;
                
                if (ff_obj.get_vertex_color(vertex) != 1)
                {
                    reachable_tag[vertex] = 1; //reachable 
                }
                else
                {
                     //stop and assign delay;
                     //gray_path_set[prime_source][vertex].delay = 
                        //vertex_arrive_time[vertex];
                }
            }
        }

        //assign path delay
        for (unsigned int j = 0; j < gray_path_set[i].size(); j++)
        {
            struct edge* gray_path = &gray_path_set[i][j];
            unsigned int v = (*gray_path).out;
            (*gray_path).delay = vertex_arrive_time[v];
        }
    }
}
void graph_reduction::partial_sta_reduce(class ff_graph& ff_obj)
{
    vector <vector <unsigned int>> critical_prime_paths;

    //iterative PERT
    for (unsigned int i = 0; i < gray_set.size(); i++) 
    {
        //ignore gray one without outgoing edges
        unsigned int prime_source = gray_set[i];

        if (ff_obj.vertex_fanout[prime_source].empty()) continue;

        //reset arrive time for each gray starting vertex
        vertex_arrive_time.assign(ff_obj.get_vertex_num(), 0); 

        //exist tag in reachable list of v_i
        vector<unsigned int> reachable_tag;
        reachable_tag.assign(ff_obj.get_vertex_num(), 0); 

        reachable_tag[prime_source] = 1; //reachable

        //PERT
        for (unsigned int vertex = prime_source + 1; 
                        vertex < ff_obj.get_vertex_num(); vertex++)
        {         
            unsigned int critical_idx = 0;
            for (unsigned int idx = 0; 
                    idx < ff_obj.vertex_fanin[vertex].size(); idx++)
            {
                //unsigned int source = (*edge_it).in;
                struct edge fanin = ff_obj.vertex_fanin[vertex][idx];
                unsigned int source = fanin.in;
                if (reachable_tag[source] == 0) continue; //not reachable

                //accumulate path delay
                float temp_delay = fanin.delay + vertex_arrive_time[source];

                //update arrive time
                if (vertex_arrive_time[vertex] <= temp_delay)
                {
                    //unmark c_tag
                    ff_obj.vertex_fanin[vertex][critical_idx].c_tag = -1;

                    //mark as critical
                    ff_obj.vertex_fanin[vertex][idx].c_tag = 1;

                    critical_idx = idx;
                    vertex_arrive_time[vertex] = temp_delay;
                }
                
                /** Implementation notes: prime path ends with gray vertexes, 
                 *  so don't tag them and other gray ones won't contribute.
                */
                if (ff_obj.get_vertex_color(vertex) != 1) 
                {
                    reachable_tag[vertex] = 1; //reachable 
                }
            }
        }

        //identify critical prime path

        for (unsigned int j = 0; j < gray_path_set[i].size(); j++)
        {
            //identify the critical path by backward search according to c_tag

            vector<unsigned int> current_critical_prime_path;

            //vertex on critical prime path
            unsigned int c_v = gray_path_set[i][j].out; 
            current_critical_prime_path.push_back(c_v);
            while (c_v != prime_source)
            {
                for (unsigned int idx = 0; 
                    idx < ff_obj.vertex_fanin[c_v].size(); idx++)
                {
                    struct edge fanin = ff_obj.vertex_fanin[c_v][idx];
                    if (fanin.c_tag == 1) //critical
                    {
                        current_critical_prime_path.push_back(fanin.in);
                        c_v = fanin.in;
                    }
                }
            }

            critical_prime_paths.push_back(current_critical_prime_path);

            //assign path delay        
            struct edge* gray_path = &gray_path_set[i][j];
            unsigned int v = (*gray_path).out;
            (*gray_path).delay = vertex_arrive_time[v];
        }

        //reset c_tag
        for (unsigned int v = 0; v < ff_obj.get_vertex_num(); v++)
        {
            vector<edge>::iterator fanin_it;
            for (fanin_it = ff_obj.vertex_fanin[v].begin(); 
                fanin_it != ff_obj.vertex_fanin[v].end(); ++fanin_it)
            {
                (*fanin_it).c_tag = -1;
            }
        }
    }

    assert(prime_path_num == critical_prime_paths.size());
    //cost reduction
    //get the vertex which is visted by the most times.
    vector <unsigned int> vertex_reach_num;
    vertex_reach_num.assign(ff_obj.get_vertex_num(), 0);

    for (unsigned int i = 0; i < prime_path_num; i++)
    {
        for (unsigned int j = 1; j < critical_prime_paths[i].size() - 1; j++)
        {   
            vertex_reach_num[critical_prime_paths[i][j]]++;
        }

        /*unsigned int source = critical_prime_paths[i].front();
        unsigned int sink = critical_prime_paths[i].back();
        for (unsigned int j = i + 1; j < prime_path_num; j++)
        {
            if (source == critical_prime_paths[j].front() &&
                sink == critical_prime_paths[j].back())
            {
                bool redundant_prime_path = true;
            }
        }*/
    }

    unsigned int critical_v; //touched by most times
    //number of critical prime paths visiting v
    unsigned int max_vertex_reach_num;

    set <unsigned int> source_reach_gray;
    set <unsigned int> sink_reach_gray;
    source_reach_gray.insert(0);
    sink_reach_gray.insert(0);

    while (source_reach_gray.size() == 1 || sink_reach_gray.size() == 1)
    {
        max_vertex_reach_num = 0; 
        source_reach_gray.clear();
        sink_reach_gray.clear();

        for (unsigned int i = 0; i < vertex_reach_num.size(); i++)
        {
            if (vertex_reach_num[i] > max_vertex_reach_num)
            {
                max_vertex_reach_num = vertex_reach_num[i];
                critical_v = i;
            }
        }
        vertex_reach_num[critical_v] = 0; 

        assert (ff_obj.get_vertex_color(critical_v) == 0);

        for (unsigned int i = 0; i < prime_path_num; i++)
        {
            if (find(critical_prime_paths[i].begin(), 
                critical_prime_paths[i].end(),critical_v) 
                != critical_prime_paths[i].end())
            {
                source_reach_gray.insert(critical_prime_paths[i].front());
                sink_reach_gray.insert(critical_prime_paths[i].back());
            }
        }
    }

    //check prime paths share the same source and dist gray vertex
    unsigned int reduced_edge_num = prime_path_num - max_vertex_reach_num +
                source_reach_gray.size() + sink_reach_gray.size();

    total_reduced_num = reduced_edge_num + total_reduced_num;

    //cout << "reduced_edge_num = " << reduced_edge_num << endl;
}

void graph_reduction::DFS_visit(class ff_graph& ff_obj, 
                            const unsigned int &vertex)
{
    color_label[vertex] = 1; //color it gray when discover

    vector<edge>::iterator edge_it;
    for (edge_it = ff_obj.vertex_fanout[vertex].begin(); 
                edge_it != ff_obj.vertex_fanout[vertex].end(); ++edge_it)
    {
        unsigned int out = (*edge_it).out;
        float residual_label = (*edge_it).delay;

        if (color_label[out] == 0 && residual_label > 0)
        //if (residual_label > 0)
        {
            argument_path.push_back(*edge_it);
            DFS_visit(ff_obj, out);
        }
    }

    color_label[vertex] = 2; // color it black when finish

    if (vertex == ff_obj.get_vertex_num() - 1)
    {
        argument_exist = true;

        //find argument _path and stop recursive 
        color_label.assign(ff_obj.get_vertex_num(), 2);

        //mark residual edge
        for (unsigned int i = 0; i < argument_path.size(); i++)
        {
            struct edge e = argument_path[i];
            unsigned int fanin = e.in;
            vector<edge>::iterator fanout_it;
            for (fanout_it = ff_obj.vertex_fanout[fanin].begin(); 
                fanout_it != ff_obj.vertex_fanout[fanin].end(); ++fanout_it)
            {
                if ((*fanout_it).out == e.out)
                {
                    (*fanout_it).delay = -1; //set as residual
                }
            }
            //cout << e.in << " ";
        }
        //cout << endl;
        argument_path.clear();
    }
}

void graph_reduction::find_s_partition(class ff_graph& ff_obj, 
                                const unsigned int &vertex)
{
    color_label[vertex] = 1; //color it gray when discover

    vector<edge>::iterator edge_it;
    for (edge_it = ff_obj.vertex_fanout[vertex].begin(); 
                edge_it != ff_obj.vertex_fanout[vertex].end(); ++edge_it)
    {
        unsigned int out = (*edge_it).out;
        float residual_label = (*edge_it).delay;

        if (residual_label > 0 && color_label[out] == 0)
        {
            partitions[out] = 1; // in s partition since edge is not residual
            find_s_partition(ff_obj, out);
        }
    }

    color_label[vertex] = 2; // color it black when finish
}

void graph_reduction::find_min_cut(class ff_graph& ff_obj)
{
    //preprocess outsourced graph, introduce S and T, S connects all start gray
    // T connects all end gray, and have to relabel end gray
    vector<edge> backup_edge_set;
    backup_edge_set = ff_obj.edge_set;
    backup_vertex_num = ff_obj.get_vertex_num();

    for (unsigned int i = 0; i < gray_set.size(); i++) 
    {
        //end gray vertex relabel
        unsigned int gray_v = gray_set[i];

        vector<edge>::iterator fanin_it;
        for (fanin_it = ff_obj.vertex_fanin[gray_v].begin(); 
            fanin_it != ff_obj.vertex_fanin[gray_v].end(); ++fanin_it)
        {
            struct edge e = *fanin_it;
            e.out = ff_obj.get_vertex_num() + i;
            ff_obj.edge_set.push_back(e);
        }

        //connect gray with fanin to T
        if (!ff_obj.vertex_fanin[gray_v].empty())
        {
            struct edge e;
            e.in = ff_obj.get_vertex_num() + i;
            e.out = ff_obj.get_vertex_num() + gray_set.size() + 1; // T' index
            ff_obj.edge_set.push_back(e);
        }

        //connect S to gray with fanout
        if (!ff_obj.vertex_fanout[gray_v].empty())
        {
            struct edge e;
            e.in = ff_obj.get_vertex_num() + gray_set.size(); // S' index
            e.out = gray_v;
            ff_obj.edge_set.push_back(e);
        }
    }

    //temp store the edge set
    vector<edge> temp_edge_set;
    for (unsigned int i = 0; i < ff_obj.edge_set.size(); i++)
    {
        struct edge e = ff_obj.edge_set[i];
        if (e.out < ff_obj.get_vertex_num() && ff_obj.get_vertex_color(e.out) == 1)
        {
            if (e.in != ff_obj.get_vertex_num() + gray_set.size())
            continue; // ignore orignial edge to gray vertex due to relabel
        }
        temp_edge_set.push_back(e);
    }

    ff_obj.edge_set = temp_edge_set;
    ff_obj.set_edge_num(temp_edge_set.size());
    ff_obj.set_vertex_num(ff_obj.get_vertex_num() + gray_set.size() + 2);
    ff_obj.gen_fanins();
    ff_obj.gen_fanouts();

    // find argument path until there is no argument path
    argument_exist = true;
    unsigned int single_source = ff_obj.get_vertex_num() - 2;
    //implementation note: 
    //use edge delay as residual edge label if 1 then not residual, -1 residual

    for (unsigned int i = 0; i < ff_obj.get_vertex_num(); i++)
    {
        vector<edge>::iterator fanout_it;
        for (fanout_it = ff_obj.vertex_fanout[i].begin(); 
            fanout_it != ff_obj.vertex_fanout[i].end(); ++fanout_it)
        {
            (*fanout_it).delay = 1;
        }
    }

    unsigned int argument_path_num = 0;
    while (argument_exist == true)
    {
        argument_exist = false;
        color_label.assign(ff_obj.get_vertex_num(), 0);
        DFS_visit(ff_obj, single_source);
        argument_path_num++;
    }

    partitions.assign(ff_obj.get_vertex_num(), 0); //T partition is 0
    color_label.assign(ff_obj.get_vertex_num(), 0);
    find_s_partition(ff_obj, single_source);

    vector <edge> min_cut_edge_set;
    for (unsigned int i = 0; i < ff_obj.edge_set.size(); i++)
    {
        struct edge e = ff_obj.edge_set[i];
        if (partitions[e.in] != partitions[e.out])
        {
            //s-t min cut edge
            //if (e.in < backup_vertex_num)
            if (e.out < backup_vertex_num)
            {
                //if (ff_obj.get_vertex_color(e.in) != 1)
                if (ff_obj.get_vertex_color(e.out) != 1)
                {
                    //ff_obj.set_vertex_color(e.in, 1);
                    ff_obj.set_vertex_color(e.out, 1);
                    min_cut_edge_set.push_back(e);
                }
            }
        }
    }

    //recover
    ff_obj.edge_set = backup_edge_set;
    ff_obj.set_edge_num(ff_obj.edge_set.size());
    ff_obj.set_vertex_num(backup_vertex_num);
    ff_obj.gen_fanins();
    ff_obj.gen_fanouts();

    gen_reach_lists(ff_obj);
}

void graph_reduction::gen_reach_lists(class ff_graph& ff_obj)
{
    prime_path_num = 0;
    gray_reach_list.clear();
    for (unsigned int i = 0; i < gray_set.size(); i++) 
    {
        set<unsigned int> current_gray_reach_list;
        current_gray_reach_list.insert(gray_set[i]);

        color_label.assign(ff_obj.get_vertex_num(), 0); //white
        //current_reach_list.clear();

        //find reachable gray vertexes from v by BFS
        queue<unsigned int> examine_queue;
        examine_queue.push(gray_set[i]);

        while (!examine_queue.empty())
        {
            unsigned int cur_v = examine_queue.front();
            vector<edge>::iterator fanout_it;
            for (fanout_it = ff_obj.vertex_fanout[cur_v].begin(); 
                fanout_it != ff_obj.vertex_fanout[cur_v].end(); ++fanout_it)
            {
                struct edge e = *fanout_it;
                if (0 == color_label[e.out]) 
                {
                    color_label[e.out] = 1;

                    if (ff_obj.get_vertex_color(e.out) == 1) //end gray v
                    {
                        current_gray_reach_list.insert(e.out);
                        //prime_path_num++;
                    }
                    else 
                    {
                        examine_queue.push(e.out);
                    }
                }
            }
            examine_queue.pop();
        }
        
        gray_reach_list.insert(current_gray_reach_list);
    }

    set<set<unsigned int> >::iterator it1;
    set<unsigned int >::iterator it2;

    for (it1 = gray_reach_list.begin(); it1 != gray_reach_list.end(); it1++)
    {
        for (it2 = (*it1).begin(); it2 != (*it1).end(); it2++)
        {
            if (it2 == (*it1).begin()) continue;
            prime_path_num++;
        }
    }

    cout<< "prime_path_num = " << prime_path_num <<endl;
}

void graph_reduction::cost_reduce(class ff_graph& ff_obj)
{

}

void graph_reduction::partial_mc_ssta(char* benchmark, unsigned int mc_num,
                                    class ff_graph& ff_obj)
{
    //load relabled partition graph
    load_vertex_delay(benchmark, ff_obj);
    load_graph(benchmark, ff_obj);

    gen_reach_lists(ff_obj); //get all paths whose delays should transmit back

    //refinement by min-cut, not a good solution 
    //find_min_cut(ff_obj);
    //cost_reduce(ff_obj);

    write_reduce_graph(benchmark, ff_obj);

    char rd_edge_delay_file[50];
    strcpy(rd_edge_delay_file, "../benchmark/BENCH/local/");
    strcat(rd_edge_delay_file, benchmark);

    strcat(rd_edge_delay_file, "_rd_edge_p2.delay"); //phase two

    ofstream ofs(rd_edge_delay_file, ios::binary);
    
    total_reduced_num = 0; //initial reduced number
    for (unsigned int n = 0; n < mc_num; n++) 
    {
        gen_mc_delay(ff_obj, n);

#ifdef COSTRD
        partial_sta_reduce(ff_obj);
#else
        partial_sta(ff_obj);
#endif
        
        //write path delays to file
        vector<vector<edge>>::iterator it1;
        vector<edge>::iterator it2;
        for (it1 = gray_path_set.begin(); it1 != gray_path_set.end(); it1++)
        {
            for (it2 = (*it1).begin(); it2 != (*it1).end(); it2++)
            {
                struct edge e = *it2;
                //floating point 4 byte long
                ofs.write(reinterpret_cast<char*>(&e.delay), 4);
            }
        }
    }
    ofs.close();

    cout<< "total edge_num = " << total_reduced_num <<endl;
}